#include <stdint.h>
#include "types.h"
#include "string.h"
#include "mmu.h"
#include "memlayout.h"
#include "console.h"
#include "kalloc.h"
#include "spinlock.h"

extern char end[];

// #define __KALLOC_TRACE

/*
 * Free page's list element struct.
 * We store each free page's run structure in the free page itself.
 */
typedef struct run {
    struct run *next;
} run_t;

kmem_t kmem;

void
alloc_init()
{
    free_range(end, IN_KSPACE(PHYSTOP));
}

/* Free the page of physical memory pointed at by v. */
static void _kfree(void *_v)
{
    /* struct run *r; */

    char *v = (char*) _v;
    if ((uint64_t)v % PGSIZE || v < (char*) IN_KSPACE(&end) || v >= (char*) IN_KSPACE(PHYSTOP))
        panic("kfree");

    /**
     * Fill with junk to catch dangling refs.
     *
     * warning: resetting the entire memory requires a lot of time.
     */
    /* memset(v, 0xcc, PGSIZE); */

    /* Your code here. */
    run_t *run_ptr = (run_t*) v;

    acquire(&kmem.lock);
    run_ptr->next = kmem.free_list;
    kmem.free_list = run_ptr;
    kmem.page_count++;
    release(&kmem.lock);
}

// wrapper for _kfree which respects __KALLOC_TRACE marco.
void kfree(void *v) {
#ifdef __KALLOC_TRACE
    cprintf("kfree: %p\n", v);
    // cprintf("1: %p\n", (uint64_t)v % PGSIZE);
    // cprintf("2: %p\n", IN_KSPACE(&end));
    // cprintf("3: %p\n", IN_KSPACE(PHYSTOP));
#endif

    _kfree(v);
}

void
free_range(void *vstart, void *vend)
{
    char *p;
    p = ROUNDUP((char *)vstart, PGSIZE);
    for (; p + PGSIZE <= (char *)vend; p += PGSIZE)
        _kfree(p);
}

/*
 * Allocate one 4096-byte page of physical memory.
 * Returns a pointer that the kernel can use.
 * Returns 0 if the memory cannot be allocated.
 */
void *
kalloc()
{
    run_t *run_ptr;

    acquire(&kmem.lock);
    run_ptr = kmem.free_list;
    if (run_ptr) {
        kmem.free_list = run_ptr->next;
        kmem.page_count--;
        /* memset(run_ptr, 0, sizeof(run_t)); */
    }
    release(&kmem.lock);

#ifdef __KALLOC_TRACE
    cprintf("kalloc: %p\n", run_ptr);
#endif

    return (void*) run_ptr;
}

void
check_free_list()
{
    struct run *p;
    if (!kmem.free_list)
        panic("kmem.free_list is a null pointer!\n");

    for (p = kmem.free_list; p; p = p->next) {
        assert((void *)p > (void *)end);
    }
}
